# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/15 19:55 
"""

"""
给定一个字符，请你找出其中不含重复字符的最长字串的长度

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


"""


def get_no_dup_sub_string(s):
    """
    得到无重复的字串
    """
    tmp = ""
    i, res = 0, 0
    while i < len(s):
        if s[i] not in tmp:
            tmp = tmp + s[i]
        else:
            tmp_list = list(tmp)
            # dup_element_index = [num for num, j in enumerate(tmp_list) if j == s[i]][0]  # 重复元素的索引
            dup_element_index = tmp_list.index(s[i]) # 重复元素的索引
            i -= (len(tmp) - 1) - dup_element_index
            """
            根据重复的位置判断i回退的步数
            """
            tmp = s[i]
        #     print('else:',tmp)
        # print(tmp)
        res = max(res, len(tmp))
        i += 1
    return res


"""
以此递增地枚举字串的起始位置，那么子串的结束位置也是递增的。
假定我们选择字符串中的第k个字符作为起始位置，并且得到了不包含重复字符的最长子串的
结束位置为rk。那么当我们选择第k+1个字符作为起始位置时，首先从k+1到rk的字符显然是不重复的，并且由于
少了原本的第k个字符，我们可以尝试继续增大rk,直到右侧出现了重复字符为止；
滑动窗口：
1.使用双指针表示字符串中的某个子串(或窗口)的左右边界，其中左指针代表着，上文中[枚举子串的起始位置]，
而右指针即为上文的rk;
2.每一步的操作中我们将左指针向右移动一格，表示我们开始枚举下一个字符作为起始位置，在移动结束后，
这个子串对应着以左指针开始的，不包含重复字符的最长子串。

在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

"""


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            #     print('occ:', occ)
            # print('i--> occ:', occ)

            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans


if __name__ == '__main__':
    s = ["abcabcbb", "bbbbb", "pwwkew", "", " ", 'au', 'dvdf']
    S = Solution()
    for i in s:
        print(i)
        print(get_no_dup_sub_string(i))
        print(S.lengthOfLongestSubstring(i))
    # print(get_no_dup_sub_string('pwwkew'))